A reusable template computing parent pointers, discovery times, and finish times for all graph components.

  • This template provides a complete, robust implementation for a recursive Depth-First Search.
  • It correctly handles disconnected graphs by iterating through all vertices and starting a new traversal if a vertex hasn't been visited yet.
  • The nested function `go` uses a `nonlocal time` variable to maintain a global clock across all recursive calls.
  • The function computes parent pointers for each vertex, forming a DFS forest that represents the traversal path.
  • It also records discovery (d) and finish (f) times, which are crucial for advanced algorithms like topological sorting and finding strongly connected components.
dfs_full.py
def dfs_full(G):
    visited, parent, d, f = set(), {}, {}, {}
    time = 0
    
    def go(u, p=None):
        nonlocal time
        visited.add(u); parent[u] = p
        time += 1; d[u] = time
        for w in G[u]:
            if w not in visited:
                go(w, u)
        time += 1; f[u] = time
        
    for s in G:
        if s not in visited:
            go(s, None)
            
    return parent, d, f